package day190706;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/7/6 下午 09:52
 * 50. Pow(x, n)
 * https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode/
 */
public class MyPow {
    public double myPow(double x, int n) {
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        if (n == -2147483648) {
            return 0;
        }
        return twoPow(x, n);
    }

    private double twoPow(double x, int n) {
        double result = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                result = result * x;
            }
            x *= x;
            n = n >> 1;
        }
        return result;
    }

    private double halfPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        double halfPow = halfPow(x, n / 2);
        if (n % 2 == 0) {
            return halfPow * halfPow;
        } else {
            return halfPow * halfPow * x;
        }
    }


}
